#include <stdio.h>
#include <stdlib.h>

typedef struct LNode
{
    int data;
    LNode *next;
} LNode, *LinkList;

//一趟遍历确定单链表最大值
// 木有问题
LNode *getMax(LinkList L)
{
    if (L == NULL || L->next == NULL)
        return NULL;
    LNode *p, *m;
    m = L->next;
    p = L->next->next; // p用于扫描链表
    while (p != NULL)
    {
        if (p->data >= m->data)
            m = p;
        p = p->next;
    }
    return m;
}

//就地逆置
LinkList reverse(LinkList &L)
{
    // -- 添加边界条件判断
    if (L == NULL || L->next == NULL || L->next->next == NULL)
        return L;
    /*
    r指向翻转后的后继结点
    p指向当前结点
    q指向当前后继结点防止丢链
    */
    LNode *p, *q, *r;
    r = L->next;
    p = r->next;
    // q = p->next; -- 这里注释了这行 q没有赋初始

    r->next = NULL;

    while (p != NULL)
    {
        q = q->next; // --q 没有初始 会报错
        p->next = r;
        r = p;
        p = q;
    }

    L->next = p;
    return L;
}

// 就地逆置
void reverse2(LinkList &L)
{
    if (L == NULL || L->next == NULL)
        return;

    LNode *pre = NULL;    // 前驱结点
    LNode *cur = L->next; // 当前结点
    LNode *next;          // 后继结点
    while (cur != NULL)
    {
        next = cur->next; // next记录当前结点的后继 防止断链
        cur->next = pre;  // 当前结点反向
        pre = cur;        // 继续遍历
        cur = next;
    }
    L->next = pre;
}

//循环单链表，第k个元素前插入，超过表长插在表尾
//完全OK q可以不要 我写下面了
bool insertLink(LinkList &L, int k, int y)
{
    LNode *p, *q; // p扫描，记录插入位置，q标记后继结点
    int j = 0;

    p = L;

    while (p->next != L && j < k - 1)
    {
        p = p->next;
        j++;
    }

    LNode *s;
    s = (LNode *)malloc(sizeof(LNode));
    q = p->next;
    s->next = q;
    p->next = s;
    s->data = y;
    return true; // -- 返回值
}

void insertLink2(LinkList &L, int k, int e)
{
    LNode *ptr = L; // 记录第k个节点的前驱
    int index = 0;  // 记录个数
    while (ptr->next != L && index < k - 1)
    {
        ptr = ptr->next;
        index++;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = ptr->next;
    ptr->next = s;
}

// 测试用

// 尾插法 并返回插入的节点
LNode *Append(LinkList head, int e)
{
    LNode *ptr = head;
    while (ptr->next)
    {
        ptr = ptr->next;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = NULL;
    ptr->next = s;
    return s;
}

// 遍历
void PrintForSingleList(LinkList head)
{
    LNode *ptr = head->next;
    printf("head->");
    while (ptr)
    {
        printf("%d->", ptr->data);
        ptr = ptr->next;
    }
    printf("null\n");
}

// 遍历 循环单链表
void PrintCircularlist(LinkList head)
{
    LNode *ptr = head->next;
    printf("head->");
    while (ptr != head)
    {
        printf("%d->", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}

int main()
{
    LinkList head;
    // init
    head = (LNode *)malloc(sizeof(LNode));
    head->next = NULL;

    // append
    Append(head, 3);
    Append(head, 6);
    Append(head, 7);
    Append(head, 2);
    Append(head, 4);
    PrintForSingleList(head);

    LNode *max = getMax(head);
    printf("The maximum value is %d\n", max->data);

    // reverse
    reverse2(head);
    PrintForSingleList(head);

    // circle
    LNode *last = Append(head, 9);
    last->next = head;
    PrintCircularlist(head);
    insertLink(head, 3, 0);
    PrintCircularlist(head);
    return 0;
}

// 输出
// head->3->6->7->2->4->null
// The maximum value is 7
// head->4->2->7->6->3->null
// head->4->2->7->6->3->9->
// head->4->2->0->7->6->3->9->